<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Sending Constraints to Multiple Solvers
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial124.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial126.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc245">17.4</A>&nbsp;&nbsp;Sending Constraints to Multiple Solvers</H2><UL>
<LI><A HREF="tutorial125.html#toc122">Syntax and Motivation</A>
<LI><A HREF="tutorial125.html#toc123">Handling Booleans with Linear Constraints</A>
<LI><A HREF="tutorial125.html#toc124">Handling Disjunctions</A>
<LI><A HREF="tutorial125.html#toc125">A More Realistic Example</A>
</UL>

<A NAME="@default425"></A>
<A NAME="toc122"></A>
<H3 CLASS="subsection"><A NAME="htoc246">17.4.1</A>&nbsp;&nbsp;Syntax and Motivation</H3>
Because of the cooperation between solvers, it is often useful to send
constraints to multiple solvers.
A linear constraint, such as <I>X</I>+2 &#8805; <I>Y</I>, can be posted to <TT>eplex</TT> by
the code <CODE>eplex: (X+2 $&gt;= Y)</CODE>. The same constraint can be posted
to <TT>ic</TT> by the code <CODE>ic: (X+2 $&gt;= Y)</CODE>. 
The constraint can be sent to both solvers by the code 
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
   [ic,eplex]: (X+2 $&gt;= Y)
</PRE></BLOCKQUOTE>
By sending constraints to both solvers, where possible, we can
improve search algorithms for solving constraint problems.
Through enhanced constraint reasoning at each node of the search tree
we can:
<UL CLASS="itemize"><LI CLASS="li-itemize">
prune the search tree, thus improving efficiency
<LI CLASS="li-itemize">render the algorithm less sensitive to search heuristics
</UL>
The second advantage is a particular benefit of combining different
solvers, as opposed to enhancing the reasoning power of a single
solver. 
See [<A HREF="tutorial133.html#RWH99"><CITE>22</CITE></A>] and [<A HREF="tutorial133.html#rodosekcp"><CITE>23</CITE></A>] for
experimental results and application examples using multiple solvers
in this way. <BR>
<BR>
<A NAME="toc123"></A>
<H3 CLASS="subsection"><A NAME="htoc247">17.4.2</A>&nbsp;&nbsp;Handling Booleans with Linear Constraints</H3>
<A NAME="@default426"></A>
The <CODE>overlap</CODE> constraint example above is disjunctive and
therefore non-linear, and is only handled by <TT>ic</TT>.
However as soon as the boolean variable is labelled to 1, during
search, the constraint becomes linear.<BR>
<BR>
The cooperation between the <TT>eplex</TT> and <TT>ic</TT> solvers could
therefore be improved by passing the resulting linear constraint to
<TT>eplex</TT> as soon as the boolean is labelled to 1.
This could be achieved using a constraint handling rule (see CHR) or a
suspended goal (see chapter <A HREF="tutorial098.html#chapimpl">14</A>).<BR>
<BR>
<A NAME="@default427"></A>
However the same improved cooperation can be achieved by a well known
mathematical programming technique (see e.g. [<A HREF="tutorial133.html#Williams99"><CITE>30</CITE></A>])
that builds the boolean variable into a linear constraint that can be
sent to <TT>eplex</TT> even before the boolean is instantiated. 
This linear constraint effectively enforces the <EM>overlap</EM>
constraint if the boolean is instantiated to 1, but does not enforce
it if the boolean is instantiated to 0.<BR>
<BR>
To achieve this we introduce sufficiently big multipliers, that when
the boolean is set to 0 the 
constraint is satisfied <EM>for all values within the variables'
bounds</EM>.
This method is known as the <EM>bigM</EM> transformation.<BR>
<BR>
It is illustrated in the following encoding
of <CODE>pos_overlap</CODE>:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
pos_overlap(Start,Duration,Time,Bool) :-
        % if Bool is 1 then the task with start time Start and
        % duration Duration overlaps time point Time
        Max1 is maxdiff(Start,Time),
        Max2 is maxdiff(Time,Start+Duration-1),      
        eplex: (Time+(1-Bool)*Max1 $&gt;= Start),              % lin1
        eplex: (Time $=&lt; Start+Duration-1+(1-Bool)*Max2).   % lin2

maxdiff(Expr1,Expr2,MaxDiff) :-
        % the maximum diffrence between Expr1 and Expr2 is the max val
        % of (Expr1 - Expr2)
        MaxDiff is max_val(Expr1 - Expr2).

max_val(Expr, Max) :-
        % the maximum value of a variable is its upper bound
        var(Expr),!,
        get_var_bounds(Expr, _, Max).
max_val(Expr, Max) :-
        % the maximum value of a number is itself
        number(Expr),!,
        Max = Expr.
max_val(Expr1 + Expr2, Max) :-
        % the maximum value of (Exrp1 + Expr2) is the maximum value of
        % Expr1 plus the maximum value of Expr2
        Max is max_val(Expr1) + max_val(Expr2).
max_val(Expr1 - Expr2, Max) :-
        % the maximum value of (Exrp1 - Expr2) is the maximum value of
        % Expr1 minus the minimum value of Expr2
        Max is max_val(Expr1) - min_val(Expr2).

min_val(Expr, Min) :-
        % the minimum value of a variable is its lower bound
        var(Expr),!,
        get_var_bounds(Expr, Min, _).
min_val(Expr, Min) :-
        % the minimum value of a number is itself
        number(Expr),!,
        Min = Expr.
min_val(Expr1 + Expr2, Max) :-
        % the minimum value of (Exrp1 + Expr2) is the minimum value of
        % Expr1 plus the minimum value of Expr2
        Max is min_val(Expr1) + min_val(Expr2).
min_val(Expr1 - Expr2, Max) :-
        % the minimum value of (Exrp1 - Expr2) is the minimum value of
        % Expr1 minus the maximum value of Expr2
        Max is min_val(Expr1) - max_val(Expr2).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
The linear constraints, which will enforce the overlap condition when
the variable <CODE>Bool</CODE> is set to 1, are labelled
<EM>lin1</EM> and <EM>lin2</EM>.
If the variable <CODE>Bool</CODE> is instantiated to 0, then the variables (or
values) <CODE>Start</CODE>, <CODE>Time</CODE> and <CODE>Duration</CODE> are free to take
any value in their respective domains.<BR>
<BR>
<A NAME="@default428"></A>
Notice that <CODE>pos_overlap</CODE> is logically weaker than <CODE>overlap</CODE>
because 
<UL CLASS="itemize"><LI CLASS="li-itemize">
it does not enforce the integrality of the boolean variable,
(i.e. <CODE>pos_overlap</CODE> is a linear relaxation of the disjunctive
constraint), and
<LI CLASS="li-itemize">it does not enforce the negation of <EM>overlap</EM> in case the
boolean is set to 0.
</UL>
The tighter cooperation is achieved simply by adding the
<CODE>pos_overlap</CODE> constraint to the original encoding:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
eplex_constraints_2(Time,S1,S2,S3,B1,B2) :-
        % task 1 with duration 3 and task 2 with duration 5 are both
        % completed before the start time of task 3
        before(S1,3,S3),
        before(S2,5,S3),
        % task 1 with duration 3 overlaps time point Time if B1 = 1
        pos_overlap(S1,3,Time,B1),
        % task 2 with duration 5 overlaps time point Time if B2 = 1
        pos_overlap(S2,5,Time,B2).

hybrid3(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 ic bounds in order to
        % suspend on changes to them
        ic: (S3::1..20),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        eplex_constraints(Time,S1,S2,S3,B1,B2),
        % perform the optimisation
        both_opt(labeling([B1,B2,S1,S2]),min(S3),End).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Although it may at first glance seem better to enforce the
integerality of all variables in the linear solver as well, this is in
fact counter-productive for variables that will be explicitly labelled
during search in hybrid algorithms. The external solver would
then perform its own branch-and-bound search in addition to the
branch-and-bound search being performed within the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> program.<BR>
<BR>
<A NAME="toc124"></A>
<H3 CLASS="subsection"><A NAME="htoc248">17.4.3</A>&nbsp;&nbsp;Handling Disjunctions</H3>
The same technique, of introducing boolean variables and sufficiently
large multipliers, can be used to translate any disjunction of linear
constraints into linear constraints (and integrality constraints on
the booleans) which can be handled by <TT>eplex</TT>.<BR>
<BR>
Consider the negation of the <EM>overlap</EM> constraints above: if a task does
not overlap a time point then it is <EM>either</EM> completed before the
time point <EM>or</EM> starts after the timepoint. This disjunction can
be expressed in <TT>eplex</TT> using two further boolean variables:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
neg_overlap(Start,Duration,Time,Bool1,Bool2) :-
        % if Bool1 is 1 then the task with start time Start and duration
        % Duration starts after time point Time
        Max1 is maxdiff(Time,Start-1),
        eplex:(Time $=&lt; Start-1+(1-Bool1)*Max1),
        % if Bool2 is 1 then the task with start time Start and duration
        % Duration is completed before time point Time
        Max2 is maxdiff(Start+Duration,Time),
        eplex:(Time+(1-Bool2)*Max2 $&gt;= Start+Duration).

eplex_constraints_3(T,S1,S2,S3,B1,N1B1,N2B1,B2,N1B2,N2B2) :-
        % task 1 with duration 3 and task 2 with duration 5 are both
        % completed before the start time of task 3
        before(S1,3,S3),
        before(S2,5,S3),
        % task 1 with duration 3 either overlaps time point Time,
        % starts after it or is completed before it
        pos_overlap(S1,3,T,B1),
        neg_overlap(S1,3,T,N1B1,N2B1),
        eplex:(N1B1+N2B1 $= 1-B1),
        % task 2 with duration 5 either overlaps time point Time,
        % starts after it or is completed before it
        pos_overlap(S2,5,T,B2),
        neg_overlap(S2,5,T,N1B2,N2B2),
        eplex:(N1B2+N2B2 $= 1-B2),
        % exactly one of task 1 with duration 3 and task 2 with
        % duration 5 overlaps time point Time
        eplex:(B1+B2 $= 1).

hybrid4(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 and the non-overlap
        % booleans ic bounds in order to suspend on changes to them
        ic:(S3::1..20),
        ic:([N1B1,N2B1,N1B2,N2B2]::0..1),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        eplex_constraints_3(Time,S1,S2,S3,B1,N1B1,N2B1,B2,N1B2,N2B2),
        % perform the optimisation
        both_opt(labeling([B1,N1B1,N2B1,B2,N1B2,N2B2,S1,S2]),min(S3),End).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Now the negation of the overlap will be enforced whenever either of
the non-overlap booleans is set to 1. Note that it is not strictly
necessary to label the non-overlap booleans: whenever the start time
of a task is labelled in such a way that the task falls to one side of
the time point, the other non-overlap boolean will be forced to 0
by its linear non-overlap constraint. The constraint requiring a task
to either overlap or fall to one side of the time point will then
force the remaining non-overlap boolean to be 1.<BR>
<BR>
In fact in this simple example we gain nothing by including the <TT>neg_overlap</TT> constraints on the &#8220;direction&#8221; of non-overlap. As soon
as a labeling decision has been made as to whether one task overlaps
the time point, the earliest possible start time of both tasks is
updated in the linear solver. Since the problem cost is minimized by
starting all tasks as early as possible, the relaxed <TT>eplex</TT>
solution will conicide with the integer solution.<BR>
<BR>
As another simple example consider a naive program to choose values for the
elements of a finite list (of length <CODE>Length</CODE>) such that each
pair of values differs by at least 2. 
The <EM>diff2</EM> constraint on each pair <CODE>X</CODE> and <CODE>Y</CODE> 
of elements can be expressed as a disjunction in <TT>ic</TT>:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
diff2ic(X,Y) :-
        % X and Y must differ by at least 2
        ic: ((X+2 $=&lt; Y) or (Y+2 $=&lt; X)).

list_diff2ic(List) :-
        % each pair must differ by at least 2
        (
            fromto(List, [X|Rest], Rest, [])
        do
            (
                foreach(Y, Rest),
                param(X)
            do
                diff2ic(X,Y)
            )
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Alternatively it can be expressed in <TT>eplex</TT> using a boolean
variable:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
diff2eplex(X,Y,Length,B) :-
        % if B is 1 then Y is at least 2 greater than X
        eplex: (X+2+B*Length $=&lt; Y+Length),
        % if B is 0 then X is at least 2 greater than Y
        eplex: (X+Length $&gt;= Y+2+(1-B)*Length).

list_diff2eplex(List, Length, Bools) :-
        % each pair must differ by at least 2
        (
            fromto(List, [X|Rest], Rest, []),
            fromto(Bools, Out, In, []),
            param(Length)
        do
            (
                foreach(Y, Rest),
                fromto(Out, [B|Bs], Bs, In),
                param(X, Length)
            do
                diff2eplex(X,Y,Length,B)
            )
        ).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Suppose each element <I>E</I> of the list must
take a value between 1 and 2*(<I>Length</I>&minus;1), 
then any attempted labelling of the elements must fail.
Sending the constraints to <TT>ic</TT> and labelling the elements of the
list is inefficient.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
ic_list(List) :-
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        ic: (List::1..Max),
        list_diff2ic(List),
        labeling(List).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Sending the constraints to <TT>eplex</TT> and enforcing integrality of
the booleans is more efficient.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
eplex_list(List) :-
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        eplex: (List::1..Max),
        list_diff2eplex(List, Length, Bools),
        % enforce Bools to be 0..1 and integer
        eplex: integers(Bools),
        eplex: (Bools::0..1),
        % setup the eplex solver with a dummy objective function
        eplex:eplex_solver_setup(min(0),Cost,[],[]),
        % solve by linear solver
        eplex:eplex_solve(Cost).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
Better still is to post the constraints to both <TT>ic</TT> and 
<TT>eplex</TT>, 
and label the booleans.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
hybrid_list(List) :-
        % give the eplex cost variable some default bounds
        ic:(Cost $:: -1.0Inf..1.0Inf),
        length(List, Length),
        Max is 2*(Length-1),
        % each element must take a value between 1 and 2*(Length-1)
        ic: (List::1..Max),
        list_diff2ic(List),
        list_diff2eplex(List, Length, Bools),
        % enforce Bools to be 0..1 (but not integer in eplex)
        ic: (Bools::0..1),
        % setup the eplex solver with a dummy objective function
        eplex:eplex_solver_setup(min(0),Cost,[sync_bounds(yes)],[ic:min,ic:max]),
        % minimize Cost by branch-and-bound
        minimize((labeling(Bools),eplex_get(cost,Cost)),Cost).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
<A NAME="toc125"></A>
<H3 CLASS="subsection"><A NAME="htoc249">17.4.4</A>&nbsp;&nbsp;A More Realistic Example</H3>
<A NAME="@default429"></A>
For more complex applications, sending all &#8220;linearisable&#8221;
constraints to both <TT>ic</TT> and <TT>eplex</TT> is rarely the best
method.
Sending too many constraints to <TT>ic</TT> can result in many wakings
but little useful propagation.
Sending too many constraints to <TT>eplex</TT> can cause a big growth
in the size of the constraint store, which slows down constraint
solving with little improvement in the relaxed optimum.
If the extra variables are constrained to be integer, then the (MIP)
solver may enter a deep search tree with disastrous consequences for
efficiency.
In this example we briefly illustrate the point, though there is no
space to include the whole program, and complete supporting results.<BR>
<BR>
Consider the problem of generating test networks for IP (internet protocol).
To generate such networks, it is necessary to assign capacities
to each line. We assume a routing algorithm that sends each
message along a &#8220;cheapest&#8221; path, where the cost is dependent
on the bandwidth.
Messages from a particular start to end node are
divided equally amongst all cheapest paths.<BR>
<BR>
<DIV CLASS="center">
<IMG SRC="tutorial045.gif"><BR>
<BR>
<BR>

<B>Path Flows</B>
</DIV><BR>
<BR>
Given a total quantity <CODE>Qty</CODE> of messages, between a particular
start and end node, it is necessary to compute the quantity of
messages <CODE>QtyP</CODE> along each path <I>P</I> between the two nodes.
The variable <CODE>CostP</CODE> represents the cost of this path, and the
variable <CODE>MinCost</CODE> represents the cost of the cheapest path.
The variable <CODE>Count</CODE> represents the number of cheapest paths
(between which the messages were equally divided).
A boolean variable <EM>BP</EM> records whether the
current path is a cheapest path, and therefore whether <CODE>QtyP</CODE>
is non-zero.
The encoding in <TT>ic</TT> is as follows:
<BLOCKQUOTE CLASS="quote"><PRE CLASS="verbatim">
ic: '$&gt;='(MinCost + 1, CostP,BP),    % con3
ic: (QtyP*Count $= BP*Qty)         % con4
</PRE></BLOCKQUOTE>
Note that it is not possible to test for equality between
<CODE>MinCost</CODE> and <CODE>CostP</CODE> because they are not integers but
real number variables.<BR>
<BR>
These constraints are very precise but propagate little until the
variables <CODE>MinCost</CODE> and <CODE>CostP</CODE> have tight bounds.<BR>
<BR>
The challenge is to find a combination of <TT>ic</TT> and <TT>eplex</TT>
constraint handling that efficiently extract the maximum information
from the constraints.
Linearising <CODE>con3</CODE> so it can be handled by <TT>eplex</TT> does not
help prune the search tree.
Worse, it 
may significantly increase the size of the linear constraint store and 
the number of integer (boolean) variables, which impacts solver
performance. <BR>
<BR>
Once all the boolean variables are instantiated, the
sum of <CODE>QtyP</CODE> for all the paths equals the total quantity
<CODE>Qty</CODE> (because precisely <EM>Count</EM> paths have a non-zero
<I>PQty</I> = <I>Qty</I> / <I>Count</I>).
We therefore introduce a variable <CODE>Qties</CODE> constrained to be the
sum of all the path quantities. If <CODE>QtyList</CODE> is a list of the
path quantities, we can express the constraint thus
<CODE>Qties $= sum(QtyList)</CODE>.
We can now add a redundant constraint <CODE>Qty $= Qties</CODE>.
The above constraints are both linear and can be handled by 
<TT>eplex</TT>.<BR>
<BR>
In practice this encoding dramatically enhances the efficiency of the 
test network generation.
Experimentation with this program revealed that posting the redundant
constraints to <TT>eplex</TT> yields a much more 
significant improvement than just posting them to <TT>ic</TT>.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
It is easy to send a constraint to more than one solver.
Even disjunctive constraints can be encoded in a form that enables
them to be sent to both solvers. 
However for large applications it is best to send constraints only to
those solvers that can extract useful information from them. This
requires experimentation.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 17.3: Sending Constraints to Multiple Solvers</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial124.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial126.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
